package com.squirrel.michale;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/1 4:11 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode2467_2 {

    List<Integer>[] g;
    int n, ans = Integer.MIN_VALUE;
    int b;
    int[] amount, bobTime;

    public int mostProfitablePath2(int[][] edges, int bob, int[] amount) {
        this.amount = amount;
        this.b = bob;
        this.n = amount.length;
        this.g = new List[n];
        this.bobTime = new int[n];
        Arrays.fill(bobTime, n);
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            g[edge[0]].add(edge[1]);
            g[edge[1]].add(edge[0]);
        }
        dfsB(bob, -1, 0);
        g[0].add(-1);
        dfsA(0, -1, 0, 0);
        return ans;
    }

    public boolean dfsB(int p, int f, int time) {
        if (p == 0) {
            bobTime[p] = time;
            return true;
        }
        for (int e : g[p]) {
            if (e != f && dfsB(e, p, time + 1)) {
                bobTime[p] = time;
                return true;
            }
        }
        return false;
    }

    public void dfsA(int p, int f, int time, int total) {
        if (bobTime[p] == time) {
            total += amount[p] / 2;
        } else if (bobTime[p] > time) {
            total += amount[p];
        }
        if (g[p].size() == 1) {
            ans = Math.max(ans, total);
        }
        for (int e : g[p]) {
            if (e != f)
                dfsA(e, p, time + 1, total);
        }
    }
}
